/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        105.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/8 10:33
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
/*
 * 根据一棵树的前序遍历与中序遍历构造二叉树。
 */
#include <unordered_map>
#include <vector>
#include "tree_node.h"
using namespace std;

class Solution {
private:
    unordered_map<int, int> index;
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int n = preorder.size();
        for (int i = 0; i < n; i++)
            index[inorder[i]] = i;
        return buildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    TreeNode *buildTree(const vector<int> &preorder, const vector<int> &inorder,
                        int pre_left/*preorder左子树起点*/, int pre_right/*preorder右子树终点*/,
                        int in_left/*inorder左子树起点*/, int in_right/*inorder右子树终点*/) {
        if (pre_left > pre_right)
            return nullptr;

        /* 根节点在preorder的序号 */
        int pre_root = pre_left;
        /* 根节点在inorder的序号 */
        int in_root = index[preorder[pre_root]];

        TreeNode *root = new TreeNode(preorder[pre_root]);
        /* 左子节点的个数 */
        int left_subtree_size = in_root - in_left;

        root->left = buildTree(preorder, inorder,
                               pre_left + 1, pre_left + left_subtree_size,
                               in_left, in_root - 1);
        root->right = buildTree(preorder, inorder,
                                pre_left + 1 + left_subtree_size, pre_right,
                                in_root + 1, in_right);
        return root;
    }
};